perm filename PROJ.F80[F80,JMC] blob
sn#622585 filedate 1981-11-04 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .REQUIRE "206MAC.PUB[206,LSP]" source_file
C00003 00003 .hd206 FALL 1981
C00006 00004 .bb Proving
C00009 00005 .bb Formal systems
C00011 00006 .bb Compiling
C00013 00007 .bb Games
C00015 00008 .bb AIish programs
C00016 00009 .bb Data manipulating programs.
C00018 00010 .bb Some previous projects.
C00019 ENDMK
C⊗;
.REQUIRE "206MAC.PUB[206,LSP]" source_file;
.
.odd heading(,,{page}) ;
.even heading({page}, , ) ;
.
.LSPFONT
.basicops
.
.allops
.itemmac 1;
.
.PORTION MAINPORTION
.hd206 FALL 1981
.PAGE ← 1
.cb TERM PROJECTS
A term project is not required in order to pass CS206 or even to
get a grade of B if your homework and exams are good enough. However, if
you wish to get some flavor of A then doing a good term project is necessary.
Term projects will be due on the day of the final exam. Any term project
turned in ahead of time will be likely to get a more thorough reading.
The term project is your opportunity to direct your attention
to and get experience in some area that interests you.
It may be programming or theoretical or both. A programming project
may be related to computing (a compiler or program transformer),
AI (game playing, problem
solving) other areas of computer science, or other suitable area
in which you have interest and expertise. A theoretical project
should relate to reasoning about LISP programs. Some ideas are
given below, but proposals for your own project will be considered.
The write-up of your project is the main thing that will get
graded so it should be clear and carefully done. It should include
a brief description of what you set out to do and what you accomplished.
If you write a progam, you should give a description of how it works
and why, including a description of the data structures it is acting
on and the basic operations on these structures. The code
for the program should be included with brief comments in appropriate
places to guide the reader. Some sample runs should also be included.
Before putting a lot of work into your project, you should
outline carefully just what you plan to do and have this approved
by the instructor or the TA. You are also encouraged to discuss
initial ideas before finalizing your plans.
.group
.bb Proving
#. Develop and apply techniques for proving properties of programs
manipulating graphs. The proofs should be fully formal, but also
natural and cleanly expressible. Some particular problems to be
considered are formalizing abstractly the notions of graph, path,
component, etc. Showing that a particular S-expression representation
of graphs satisfy the same properties as the abstract notion. Developing
principles for proving that programs on graphs terminate. Specifying
and proving correctness of some graph programs (list all nodes, find a
path from ⊗v1 to ⊗v2, find the shortest path, etc.
[Remark: for a term project you expected only to solve a select few of
these problems, not all of them.]
#. Develop the theory of re-entrant list structures. (see Chapter IV.)
Decide on a representation
of such structures as ordinary lists (say with pointers and labels). Define
some primitive operations (for example: ⊗⊗car cdr cons point cut⊗). Write programs
to go from one representation to the other. Write an equality predicate in
for structures in your representation. An induction schema to
for proving facts about programs on such structures will be discussed
in class.
Write some interesting programs on such structures and prove some facts
about them.
#. Prove a moderate size "practical" program correct. For example
a modest pattern matcher, unifier, simple production rule system, or
game player would be appropriate.
#. Theory of %2qif x1=x2 qthen x3 qelse x4%1. This form of
conditional expression should admit additional canonical forms
beyond those for %2qif p qthen a qelse b%1 discussed in
(McCarthy 1963). A good term paper would be devising a canonical
form, writing a program to reduce expressions to canonical form
and proving that it does so. See also (Boyer and Moore 1980).
.apart
.group
.bb Formal systems
#. Write a proof checker for a simple formal system. Some examples
of suitable formal systems are:
.skip
.begin preface 0 indent 8,8
##. Trigonometric expressions: using trig identities to prove expressions
equivalent.
##. Symbolic integration: using various standard tricks for manipulating
integrands into integrable form.
##. Propositional logic and a Hilbert or natural deduction style proof
system.
.skip
Some "bells and whistles" that you might consider adding to your system
include:
.skip
##. Implement some heuristics to search for proofs.
##. Implement some derived rules plus the ability to expand a deduction
using the derived rule into one consisting only of elementary steps.
.end
.apart
.group
.bb Compiling
.begin indent 0,4
#. Improve the LCOM4 compiler. Some possibilities are to modify LCOM4 to:
.begin nofill indent 8,8
##. compile ⊗label.
##. handle the %3prog%1 and related features.
##. handle functions as arguments (as for ⊗mapcar) .
##. recognize iteration and compile it with loops.
##. produce more efficient arithmetic code.
##. compile additional features such as "while's" or "do's" etc..
.end
#. Write a data driven compiler for LISP.
#. Write a syntax directed compiler for LISP. Perhaps several passes using
an intermediate language would be useful.
.apart
.group
.bb Games
#. Write a program to play a game. Some possible games are:
.begin nofill indent 8,8
##. 3-dimensional Tic Tac Toe (See Chapter VII for 2-D version.)
##. Sequence solitaire
##. Mastermind
##. Otello
.end
#. Queen and King against Rook and King in chess. In CS204 this
quarter, the students wrote programs to solve the problem by
brute force data processing. A program using the methods of
(Huberman 1969) can be checked against the giant tables produced
by the data-processing solution. If you wish to try this problem,
discuss it with me first.
There are two key issues in programs to play games. One is
the method used to prune the search for possible moves, the other
is developing good strategies of choosing moves. These issues are,
of course, not mutually independent.
Proving the correctness of a significant game playing program would
be especially appreciated.
Be sure to hold individual test runs to a few seconds. It is easy to
use large amounts of computer time in such projects.
.apart
.group
.bb AIish programs
#. Write a program that generates form letters. You should have
a particular class of user in mind, say a business, or political group.
It should deal with a variety of situations and the resulting letter
should depend in an interesting way on set of facts about recipient of letter.
#. A natural language program, for example a program that does
morphemic analysis of English. You should have a clearly defined
class of words that can be analyzed by your program.
.apart
.group
.bb Data manipulating programs.
#. Write a program that does file cross referencing for some
interesting class of files.
#. Answering questions about a data base of facts.
Assume you have a finite domain of objects and a data base
of facts about these objects. For example assume that there is a given
collection of relations that apply to the objects and
all true instances of these relations are in the data base.
(The closed world assumption.) Write a program that decides the
truth or falsity of any first order sentence built from the given
relation symbols, variables and names of the objects. An interesting
and useful extension is to allow a formula with one free variable
and have the program return one or more objects (if any) that satisfy
the formula.
.apart
.group
.bb Some previous projects.
#. Minimizing finite state machines
#. Digital Circuit design: design representation of gates and
circuits. Implement algorithms for optimizing circuit designs or layouts.
#. LALR parser
.end
.apart